Zigzag Poset

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a fence, also called a zigzag poset, is a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

(poset) in which the order relations form a path with alternating orientations: :

a

ceh or : $a>b d f i \cdots$ A fence may be
finite Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or marke ...
, or it may be formed by an infinite alternating sequence extending in both directions. The incidence posets of
path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
s form examples of fences. A
linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...
of a fence is called an
alternating permutation In combinatorial mathematics, an alternating permutation (or zigzag permutation) of the set is a permutation (arrangement) of those numbers so that each entry is alternately greater or less than the preceding entry. For example, the five alte ...
; André's problem of counting the number of different linear extensions has been studied since the 19th century. The solutions to this counting problem, the so-called Euler zigzag numbers or up/down numbers, are: : $1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042.$ :. The number of
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
s in a fence is a
Fibonacci number In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
; the
distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...
with this many elements, generated from a fence via
Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...
, has as its graph the
Fibonacci cube In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs ...
. A partially ordered set is series-parallel if and only if it does not have four elements forming a fence. Several authors have also investigated the number of
order-preserving map In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of orde ...
s from fences to themselves, or to fences of other sizes. An up-down poset is a generalization of a zigzag poset in which there are downward orientations for every upward one and total elements.. For instance, has the elements and relations : $a>b>c e>f h>i.$ In this notation, a fence is a partially ordered set of the form .

Equivalent conditions
The following conditions are equivalent for a poset : # is a
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of zigzag posets. #If in , either or . # $< \circ < \; = \emptyset$ , i.e. it is never the case that and , so that is vacuously transitive. # has dimension at most one (defined analogously to the
Krull dimension In commutative algebra, the Krull dimension of a commutative ring ''R'', named after Wolfgang Krull, is the supremum of the lengths of all chains of prime ideals. The Krull dimension need not be finite even for a Noetherian ring. More generally t ...
of a
commutative ring In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
). #Every element of is either maximal or minimal. #The
slice category In mathematics, specifically category theory, an overcategory (and undercategory) is a distinguished class of categories used in multiple contexts, such as with covering spaces (espace etale). They were introduced as a mechanism for keeping track ...
is
cartesian closed In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in math ...
. The
prime ideal In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together with ...
s of a commutative ring , ordered by inclusion, satisfy the equivalent conditions above if and only if has Krull dimension at most one.

Notes

References
* . * . * . * . * . * . * . * . * . * . * . * Exercise 3.23a, page 157. * .

External links
* {{mathworld, title=Fence Poset, urlname=FencePoset Order theory Enumerative combinatorics